#define _CRT_SECURE_NO_WARNINGS 1
#include "heap2.h"
#include <time.h>

////树的表示方法：左孩子右兄弟法
//typedef int treedatatype;
//typedef struct tree
//{
//	treedatatype val;
//	struct tree* _leftchild;
//	struct tree* _rightborther;
//}tree;
//
////二叉树的链式存储
////二叉链
//typedef int BinarryTreeDataType;
//typedef struct BinarryTreeNode
//{
//	int data;
//	struct BinarryTreeNode* _leftchild;
//	struct BinarryTreeNode* _rightchild;
//}BTNode;
//
////三叉链
//typedef int BinarryTreeDataType;
//typedef struct BinarryTreeNode
//{
//	int data;
//	struct BinarryTreeData* _parent;
//	struct BinarryTreeNode* _leftchild;
//	struct BinarryTreeNode* _rightchild;
//}BTNode;

void test01()
{
	int a[] = { 7,2,6,4,5,8,9,1};
	int sz = sizeof(a) / sizeof(a[0]);

	Heap hp = { 0 };
	HeapInit(&hp);

	//插入数据，建堆
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		HeapPush(&hp, a[i]);
	}

	//插入数据
	//HeapPush(&hp, 0);

	//删除堆顶数据
	HeapPop(&hp);

	//获取堆顶数据
	printf("%d ", GetHeapTop(&hp));

	//获取元素个数
	printf("%d ", GetHeapSize(&hp));

	//判空
	printf("%d ", HeapEmpty(&hp));

	HeapDestroy(&hp);
}

void HeapSort(int* a, int size)
{
	assert(a);

	//建堆
	//升序，建大堆
	//降序，建小堆

	////向上调整建堆
	//int i = 0;
	//for (i = 1; i < size; i++)
	//{
	//	AdjustUp(a, i);
	//}

	//向下调整建堆
	int i = 0;
	for (i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, size);
	}

	//交换数据，并向下调整
	int end = size - 1;
	while (end)
	{
		//交换数据
		Swap(&a[0], &a[end]);

		//向下调整
		AdjustDown(a, 0, end);

		end--;
	}
}

//构造数据
void CreatData()
{
	//打开文件
	FILE* pf = fopen("data.txt", "w");
	if (pf == NULL)
	{
		perror("fopen");
		return;
	}

	//生成100000个随机数
	srand((unsigned)time(NULL));
	int n = 1;
	while (n--)
	{
		int x = rand() % 10000000;//防止随机数超过1000000
		fprintf(pf, "%d\n", x);
	}

	//关闭文件
	fclose(pf);
	pf = NULL;
}

//TOP-K问题
void Top_k(int k)
{
	//打开文件
	FILE* pf = fopen("data.txt", "r");
	if (pf == NULL)
	{
		perror("fopen");
		return;
	}

	//取前十个数
	int a[10] = { 0 };
	int i = 0;
	for (i = 0; i < 10; i++)
	{
		fscanf(pf, "%d", &a[i]);
	}

	//建成小堆
	for (i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, k);
	}

	int x = 0;
	while (fscanf(pf, "%d", &x) != EOF)
	{
		if (a[0] < x)
		{
			//交换
			Swap(&a[0], &x);

			//向下调整
			AdjustDown(a, 0, k);
		}
	}

	printf("前10个数为：");
	for (i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}

	//关闭文件
	fclose(pf);
	pf = NULL;
}

int main()
{
	//test01();


	//int a[] = { 2,6,4,5,8,9,7};
	//int sz = sizeof(a) / sizeof(a[0]);
	//堆排序
	//HeapSort(a, sz);

	////构造数据
	//CreatData();

	printf("请输入k->:  ");
	int k = 0;
	scanf("%d", &k);
	Top_k(k);

	return 0;
}